{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[7 9 5 3 8 6 2 1 4]\n",
      " [6 8 1 2 4 9 7 5 3]\n",
      " [2 4 3 5 7 1 9 6 8]\n",
      " [8 7 6 9 5 4 1 3 2]\n",
      " [3 5 9 8 1 2 4 7 6]\n",
      " [1 2 4 6 3 7 5 8 9]\n",
      " [9 1 7 4 6 8 3 2 5]\n",
      " [5 6 2 7 9 3 8 4 1]\n",
      " [4 3 8 1 2 5 6 9 7]] --------- Answer\n",
      "\n",
      "[[7 9 5 3 8 6 2 1 4]\n",
      " [6 8 1 2 4 9 7 5 3]\n",
      " [2 4 3 5 7 1 9 6 8]\n",
      " [8 7 6 9 5 4 1 3 2]\n",
      " [3 5 9 8 1 2 4 7 6]\n",
      " [1 2 4 6 3 7 5 8 9]\n",
      " [9 1 7 4 6 8 3 2 5]\n",
      " [5 6 2 7 9 3 8 4 1]\n",
      " [4 3 8 1 2 5 6 9 7]]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "\n",
    "class NaiveSodukuGenerator:\n",
    "\tdef __init__(self) -> None:\n",
    "\t\tself.pz = np.zeros((9,9), dtype=int)\n",
    "\t\t\n",
    "\tdef PossibleValueAtPosition(self, row:int, col:int):\n",
    "\t\tr = row//3*3\n",
    "\t\tc = col//3*3\n",
    "\t\treturn {1,2,3,4,5,6,7,8,9}.difference(set(self.pz[r:r+3,c:c+3].flat\\\n",
    "\t\t\t)).difference(set(self.pz[row,:])).difference(set(self.pz[:,col]))\n",
    "\n",
    "\tdef Solution_Count(self, pz, n:int, Nof_solution:int):\n",
    "\t\tif Nof_solution > 1:\n",
    "\t\t\treturn Nof_solution\n",
    "\t\tif n>=81:\n",
    "\t\t\tNof_solution+=1\n",
    "\t\t\treturn Nof_solution\n",
    "\t\t(row,col) = divmod(n,9)\n",
    "\t\tif pz[row][col] > 0:\n",
    "\t\t\tNof_solution = self.Solution_Count(pz, n+1, Nof_solution)\n",
    "\t\telse:\n",
    "\t\t\tl = self.PossibleValueAtPosition( row,col)\n",
    "\t\t\tfor v in l:\n",
    "\t\t\t\tpz[row][col] = v\n",
    "\t\t\t\tNof_solution = self.Solution_Count(pz, n+1, Nof_solution)\n",
    "\t\t\t\tpz[row][col] = 0\n",
    "\t\t\n",
    "\t\treturn Nof_solution\t\n",
    "\n",
    "\tdef SudokuSolver(self, n:int):\n",
    "\t\tif n==81:\n",
    "\t\t\treturn True\n",
    "\t\t(row,col) = divmod(n,9)\n",
    "\t\tif self.pz[row][col]>0:\n",
    "\t\t\tif self.SudokuSolver(self.pz, n+1):\n",
    "\t\t\t\treturn True\n",
    "\t\telse:\n",
    "\t\t\tl = list(self.PossibleValueAtPosition( row,col))\n",
    "\t\t\trandom.shuffle(l)\n",
    "\t\t\tfor v in l:\n",
    "\t\t\t\tself.pz[row][col] = v\n",
    "\t\t\t\tif self.SudokuSolver(n+1):\n",
    "\t\t\t\t\treturn True\n",
    "\t\t\t\tself.pz[row][col] = 0\n",
    "\t\treturn False\n",
    "\n",
    "\tdef DigHoles(self,  randomlist, n:int):\n",
    "\t\tif n >= 81:\n",
    "\t\t\treturn\n",
    "\t\t(row,col) = divmod(randomlist[n],9)\n",
    "\t\tif self.pz[row][col]>0:\n",
    "\t\t\tpz_check = self.pz.copy()\n",
    "\t\t\tpz_check[row][col]=0\n",
    "\t\t\tNof_solution = self.Solution_Count(pz_check, 0, 0)\n",
    "\t\t\tif Nof_solution == 1:\n",
    "\t\t\t\tself.pz[row][col]=0\n",
    "\t\t\t\tprint(self.pz)\n",
    "\t\t\t\tprint(\"{} zeros\".format(sum(self.pz.flat==0)))\n",
    "\t\t\t\tprint()\n",
    "\t\tself.DigHoles(randomlist, n+1)\n",
    "\n",
    "\tdef createSoduku(self):\n",
    "\t\tself.SudokuSolver(0)\n",
    "\t\tprint(self.pz, \"--------- Answer\\n\")\n",
    "\t\trandomlist = list(range(81))\n",
    "\t\trandom.shuffle(randomlist)\n",
    "\t\tself.DigHoles(randomlist, 0)\n",
    "\t\tprint(self.pz)\n",
    "\t\t\n",
    "\n",
    "\t# def main():\n",
    "\t# \tpuzzle = np.zeros((9,9), dtype=int)\n",
    "\t# \tSudokuSolver(puzzle, 0)\n",
    "\t# \tprint(puzzle, \"--------- Answer\\n\")\n",
    "\t# \trandomlist = list(range(81))\n",
    "\t# \trandom.shuffle(randomlist)\n",
    "\t# \tDigHoles(puzzle, randomlist, 0)\n",
    "\t# \treturn puzzle\n",
    "\n",
    "NaiveS = NaiveSodukuGenerator()\n",
    "NaiveS.createSoduku()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         872194 function calls (723383 primitive calls) in 0.803 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "88222/321    0.173    0.000    0.404    0.001 copy.py:128(deepcopy)\n",
      "    34545    0.116    0.000    0.116    0.000 2743691208.py:60(<listcomp>)\n",
      "29211/321    0.110    0.000    0.397    0.001 copy.py:200(_deepcopy_list)\n",
      "19430/441    0.097    0.000    0.358    0.001 2743691208.py:49(eliminate)\n",
      " 6963/364    0.089    0.000    0.345    0.001 2743691208.py:56(<listcomp>)\n",
      "   116800    0.035    0.000    0.035    0.000 {method 'append' of 'list' objects}\n",
      "    29211    0.028    0.000    0.046    0.000 copy.py:242(_keep_alive)\n",
      "   176604    0.026    0.000    0.026    0.000 {method 'get' of 'dict' objects}\n",
      " 3537/401    0.023    0.000    0.364    0.001 2743691208.py:42(fill)\n",
      "    161/1    0.022    0.000    0.778    0.778 2743691208.py:65(reSlove)\n",
      "   146965    0.021    0.000    0.021    0.000 {built-in method builtins.id}\n",
      "   122188    0.016    0.000    0.016    0.000 {built-in method builtins.len}\n",
      " 3477/341    0.016    0.000    0.360    0.001 2743691208.py:45(<listcomp>)\n",
      "    59011    0.011    0.000    0.011    0.000 copy.py:182(_deepcopy_atomic)\n",
      "     7346    0.008    0.000    0.011    0.000 2743691208.py:72(<genexpr>)\n",
      "    16697    0.007    0.000    0.007    0.000 {method 'remove' of 'list' objects}\n",
      "    10602    0.002    0.000    0.003    0.000 {built-in method builtins.all}\n",
      "      160    0.002    0.000    0.014    0.000 {built-in method builtins.min}\n",
      "        1    0.001    0.001    0.029    0.029 2743691208.py:36(preProcess)\n",
      "      646    0.000    0.000    0.001    0.000 2743691208.py:66(<genexpr>)\n",
      "      160    0.000    0.000    0.000    0.000 copy.py:66(copy)\n",
      "      160    0.000    0.000    0.000    0.000 {method 'copy' of 'list' objects}\n",
      "        1    0.000    0.000    0.806    0.806 {built-in method builtins.exec}\n",
      "       81    0.000    0.000    0.000    0.000 2743691208.py:30(<listcomp>)\n",
      "        1    0.000    0.000    0.806    0.806 2743691208.py:26(solveSudoku)\n",
      "        1    0.000    0.000    0.806    0.806 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 2743691208.py:16(oneLine2List)\n",
      "       10    0.000    0.000    0.000    0.000 2743691208.py:31(<genexpr>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}"
     ]
    }
   ],
   "source": [
    "# 作者：Icybee\n",
    "\n",
    "import copy\n",
    "import random\n",
    "class Sudoku:\n",
    "    # @param board, a 9x9 2D array\n",
    "    # Solve the Sudoku by modifying the input board in-place.\n",
    "    # Do not return any value.\n",
    "    def __init__(self):\n",
    "        self.grids = [(i,j) for j in range(9) for i in range(9)]\n",
    "        self.peercross = [[[[(j,i) for i in range(9)],[(i,k) for i in range(9)],[(j - j % 3 + i // 3,k - k % 3 + i % 3)for i in range(9)]] for k in range(9)]for j in range(9)]\n",
    "        self.peers = [[set(sum(self.peercross[j][k],[])) - set([(j,k)]) for k in range(9)] for j in range(9)]\n",
    "        self.finalsolution = False\n",
    "    \n",
    "    # convert Line to list\n",
    "    def oneLine2List(self, line):\n",
    "        if len(line) != 81:\n",
    "            print(\"Unable to Load Line(Length !=81)\")\n",
    "            return None\n",
    "        else:\n",
    "            board = []\n",
    "            for i in range(0,81,9):\n",
    "                board.append(line[i:i+9])\n",
    "            return board\n",
    "\n",
    "    def solveSudoku(self, board):\n",
    "        if not isinstance(board, list):\n",
    "            board = self.oneLine2List(board)\n",
    "        self.finalsolution = False\n",
    "        possiblenumbers = [[[i for i in range(1,10)]for j in range(9) ]for k in range(9)]\n",
    "        assert (len(board) == 9 and all((len(board[i]) == 9) for i in range(9))) == True\n",
    "        if not self.preProcess(board,possiblenumbers):return False\n",
    "        self.reSlove(possiblenumbers,1)\n",
    "        return self.finalsolution\n",
    "\n",
    "    def preProcess(self,board,possiblenumbers):\n",
    "        for i in range(81):\n",
    "            if not self.fill(i // 9,i % 9,board[i // 9][i % 9],possiblenumbers):\n",
    "                return False\n",
    "        return True\n",
    "    #@return whether the value can be filled in the current grid\n",
    "    def fill(self,x,y,value,possiblenumbers):\n",
    "        if value not in range(1,10) and value not in \"123456789\":return True\n",
    "        if int(value) not in possiblenumbers[x][y] or x not in range(9) or y not in range(9):return False\n",
    "        if len(possiblenumbers[x][y]) == 1 or all([self.eliminate(x,y,i,possiblenumbers) for i in  [j for j in possiblenumbers[x][y] if j != int(value)]]):\n",
    "            return True\n",
    "        return False\n",
    "    #@return whether elimatesuccess or not\n",
    "    def eliminate(self,x,y,value,possiblenumbers):\n",
    "        if value not in possiblenumbers[x][y]:\n",
    "            return True\n",
    "        if len(possiblenumbers[x][y]) == 1:\n",
    "            return False\n",
    "        possiblenumbers[x][y].remove(value)\n",
    "        #stg1\n",
    "        if len(possiblenumbers[x][y]) == 0 or len(possiblenumbers[x][y]) == 1 and  not all([self.eliminate(i,j,possiblenumbers[x][y][0],possiblenumbers) for (i,j) in self.peers[x][y] if (possiblenumbers[x][y][0]) in possiblenumbers[i][j]]):\n",
    "             return False\n",
    "        #stg2\n",
    "        for k in self.peercross[x][y]:\n",
    "            tem = [(i,j) for (i,j) in k if value in possiblenumbers[i][j]]\n",
    "            if len(tem) == 1 and len(possiblenumbers[tem[0][0]][tem[0][1]]) > 1 and  not self.fill(tem[0][0],tem[0][1],value,possiblenumbers):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def reSlove(self,possiblenumbers,deepth):\n",
    "        if all(len(possiblenumbers[i][j]) == 1 for (i,j) in self.grids):\n",
    "            if not self.finalsolution:\n",
    "                self.finalsolution = copy.deepcopy(possiblenumbers)\n",
    "            else:\n",
    "                self.finalsolution = True\n",
    "            return\n",
    "        length,x,y = min((len(possiblenumbers[i][j]),i,j) for (i,j) in self.grids if len(possiblenumbers[i][j]) > 1)\n",
    "        posibility = copy.copy(possiblenumbers[x][y])\n",
    "        for i in posibility:\n",
    "            copyindex = copy.deepcopy(possiblenumbers)\n",
    "            if self.fill(x,y,i,copyindex) and self.finalsolution != True:\n",
    "                self.reSlove(copyindex,deepth + 1)\n",
    "        return\n",
    "\n",
    "    def generateSolvedSudo(self):\n",
    "        self.finalsolution = False\n",
    "        possiblenumbers = [[[i for i in range(1,10)] for j in range(9) ]for k in range(9)]\n",
    "        self.reGenerate(possiblenumbers)\n",
    "        return [[str(self.finalsolution[i][j][0]) for j in range(9)] for i in range(9)]\n",
    "\n",
    "    def reGenerate(self,possiblenumbers):\n",
    "         if all(len(possiblenumbers[i][j]) == 1 for (i,j) in self.grids):\n",
    "            self.finalsolution = copy.deepcopy(possiblenumbers)\n",
    "            return True\n",
    "         length,x,y = random.choice([(len(possiblenumbers[i][j]),i,j) for (i,j) in self.grids if len(possiblenumbers[i][j]) == (min(len(possiblenumbers[x][y]) for (x,y) in self.grids if len(possiblenumbers[x][y]) > 1))])\n",
    "         posibility = copy.copy(possiblenumbers[x][y])\n",
    "         for i in posibility:\n",
    "            copyindex = copy.deepcopy(possiblenumbers)\n",
    "            if self.fill(x,y,i,copyindex) and self.finalsolution != True:\n",
    "                if self.reGenerate(copyindex):\n",
    "                    return True\n",
    "         return False\n",
    "\n",
    "    #The most simple way to generate a puzzle\n",
    "    def generateUnsolvedPuzzle(self):\n",
    "        solvedPuzzle = self.generateSolvedSudo()\n",
    "        ran = copy.deepcopy(self.grids)\n",
    "        random.shuffle(ran)\n",
    "        for (i,j) in ran:\n",
    "            buffer = solvedPuzzle[i][j]\n",
    "            solvedPuzzle[i][j] = '.'\n",
    "            if self.solveSudoku(solvedPuzzle) == True:\n",
    "                solvedPuzzle[i][j] = buffer\n",
    "        return [''.join(i) for i in solvedPuzzle]\n",
    "\n",
    "    #a little complicated way to generate a symetry sudoky puzzle\n",
    "    def generateCentralSymmetryPuzzle(self):\n",
    "        solvedPuzzle = self.generateSolvedSudo()\n",
    "        ran = copy.deepcopy([self.grids[i] for i in range(len(self.grids) // 2 + 1)])\n",
    "        random.shuffle(ran)\n",
    "        for (i,j) in ran:\n",
    "            buffer1 = solvedPuzzle[i][j]\n",
    "            buffer2 = solvedPuzzle[8 - i][8 - j]\n",
    "            solvedPuzzle[i][j] = '.'\n",
    "            solvedPuzzle[8 - i][8 - j] =  '.'\n",
    "            if self.solveSudoku(solvedPuzzle) == True:\n",
    "                solvedPuzzle[i][j] = buffer1\n",
    "                solvedPuzzle[8 - i][8 - j] = buffer2\n",
    "        return [''.join(i) for i in solvedPuzzle]\n",
    "        \n",
    "    #show the puzzle\n",
    "    def show(self,puzzle):\n",
    "        for i in range(len(puzzle)):\n",
    "            for j in range(len(puzzle[i])):\n",
    "                if puzzle[i][j] is chr:\n",
    "                    print(puzzle[i][j],end = '  ')\n",
    "                else:\n",
    "                    print(puzzle[i][j][0], end = '  ')\n",
    "                if j == 2 or j == 5 or j == 8:\n",
    "                    print('|' ,end = \"  \")\n",
    "            print(\"\")\n",
    "            if i == 2 or i == 5:\n",
    "                print('-' * 34)\n",
    "        print(\"\")\n",
    "s = Sudoku()\n",
    "# print('--------------answer-------------')\n",
    "    #print  s.solveSudoku(['.7.8....2', '.6.9...3.', '.......47', '....1..89', '.8.4.....', '.....2...', '7.93.....', '1...75.9.', '3.......1'])\n",
    "    # puzzle = s.generateCentralSymmetryPuzzle()\n",
    "# puzzle = s.generateUnsolvedPuzzle()\n",
    "# s.show(puzzle)\n",
    "# print(puzzle)\n",
    "# sudoku_string_1 = \"030467050920010006067300148301006027400850600090200400005624001203000504040030702\"\n",
    "sudoku_string_1 = \"004700020200008000000260010000900102100000005709003000030054000000800003020007800\"\n",
    "sudoku_string_2 = \"800000000003600000070090200050007000000045700000100030001000068008500010090000400\"\n",
    "sudoku_string_2 = sudoku_string_2.replace(\"0\", \".\")\n",
    "# %prun s.show(s.solveSudoku(sudoku_string_1))\n",
    "%prun s.solveSudoku(sudoku_string_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "9\n",
      "18\n",
      "27\n",
      "36\n",
      "45\n",
      "54\n",
      "63\n",
      "72\n"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------answer--------\n",
      "[[[5], [1], [9], [7], [4], [8], [6], [3], [2]], [[7], [8], [3], [6], [5], [2], [4], [1], [9]], [[4], [2], [6], [1], [3], [9], [8], [7], [5]], [[3], [5], [7], [9], [8], [6], [2], [4], [1]], [[2], [6], [4], [3], [1], [7], [5], [9], [8]], [[1], [9], [8], [5], [2], [4], [3], [6], [7]], [[9], [7], [5], [8], [6], [3], [1], [2], [4]], [[8], [3], [2], [4], [9], [1], [7], [5], [6]], [[6], [4], [1], [2], [7], [5], [9], [8], [3]]]\n"
     ]
    }
   ],
   "source": [
    "import copy\n",
    "class Solution:\n",
    "    # @param board, a 9x9 2D array\n",
    "    # Solve the Sudoku by modifying the input board in-place.\n",
    "    # Do not return any value.\n",
    "    def cross(self,A,B):\n",
    "        \"Cross product of elements in A amd elements in B\"\n",
    "        return [a + b for a in A for b in B]\n",
    "    def __init__(self):\n",
    "        self.grids = [(i,j) for j in range(9) for i in range(9)]\n",
    "        self.peercross = [[[[(j,i) for i in range(9)],[(i,k) for i in range(9)],[(j - j % 3 + i // 3,k - k % 3 + i % 3)for i in range(9)]] for k in range(9)]for j in range(9)]\n",
    "        self.peers = [[set(sum(self.peercross[j][k],[])) - set([(j,k)]) for k in range(9)] for j in range(9)]\n",
    "        self.finalsolution = False\n",
    "    def solveSudoku(self, board):\n",
    "        self.finalsolution = False\n",
    "        possiblenumbers = [[[i for i in range(1,10)]for j in range(9) ]for k in range(9)]\n",
    "        assert (len(board) == 9 and all((len(board[i]) == 9) for i in range(9))) == True\n",
    "        if not self.preProcess(board,possiblenumbers):return False\n",
    "        self.reSlove(possiblenumbers,1)\n",
    "        return self.finalsolution\n",
    "    def preProcess(self,board,possiblenumbers):\n",
    "        for i in range(81):\n",
    "            if not self.fill(i // 9,i % 9,board[i // 9][i % 9],possiblenumbers):\n",
    "                return False\n",
    "        return True\n",
    "    #@return whether the value can be filled in the current grid\n",
    "    def fill(self,x,y,value,possiblenumbers):\n",
    "        if value not in range(1,10) and value not in \"123456789\":return True\n",
    "        if int(value) not in possiblenumbers[x][y] or x not in range(9) or y not in range(9):return False\n",
    "        if len(possiblenumbers[x][y]) == 1 or all([self.eliminate(x,y,i,possiblenumbers) for i in  [j for j in possiblenumbers[x][y] if j != int(value)]]):\n",
    "            return True\n",
    "        return False\n",
    "    #@return whether elimatesuccess or not\n",
    "    def eliminate(self,x,y,value,possiblenumbers):\n",
    "        if value not in possiblenumbers[x][y]:\n",
    "            return True\n",
    "        if len(possiblenumbers[x][y]) == 1:\n",
    "            return False\n",
    "        possiblenumbers[x][y].remove(value)\n",
    "        #stg1\n",
    "        if len(possiblenumbers[x][y]) == 0 or len(possiblenumbers[x][y]) == 1 and  not all([self.eliminate(i,j,possiblenumbers[x][y][0],possiblenumbers) for (i,j) in self.peers[x][y] if (possiblenumbers[x][y][0]) in possiblenumbers[i][j]]):\n",
    "             return False\n",
    "        #stg2\n",
    "        for k in self.peercross[x][y]:\n",
    "            tem = [(i,j) for (i,j) in k if value in possiblenumbers[i][j]]\n",
    "            if len(tem) == 1 and len(possiblenumbers[tem[0][0]][tem[0][1]]) > 1 and  not self.fill(tem[0][0],tem[0][1],value,possiblenumbers):\n",
    "                return False\n",
    "        return True\n",
    "    def reSlove(self,possiblenumbers,deepth):\n",
    "        if all(len(possiblenumbers[i][j]) == 1 for (i,j) in self.grids):\n",
    "            if not self.finalsolution:\n",
    "                self.finalsolution = copy.deepcopy(possiblenumbers)\n",
    "            else:\n",
    "                self.finalsolution = True\n",
    "            return\n",
    "        length,x,y = min((len(possiblenumbers[i][j]),i,j) for (i,j) in self.grids if len(possiblenumbers[i][j]) > 1)\n",
    "        posibility = copy.copy(possiblenumbers[x][y])\n",
    "        for i in posibility:\n",
    "            copyindex = copy.deepcopy(possiblenumbers)\n",
    "            if self.fill(x,y,i,copyindex) and self.finalsolution != True:\n",
    "                self.reSlove(copyindex,deepth + 1)\n",
    "        #print('deepth: %s ' %deepth)\n",
    "        return\n",
    "s = Solution()\n",
    "print('-------answer--------')\n",
    "print(s.solveSudoku([\"..9748...\",\"7........\",\".2.1.9...\",\"..7...24.\",\".64.1.59.\",\".98...3..\",\"...8.3.2.\",\"........6\",\"...2759..\"]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linked list made in 0.3249 seconds.\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m/Users/apple/Desktop/Python 储蓄罐/Untitled Folder/Soduku.ipynb Cell 7\u001b[0m in \u001b[0;36m<cell line: 290>\u001b[0;34m()\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=277'>278</a>\u001b[0m sudoku \u001b[39m=\u001b[39m [\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=278'>279</a>\u001b[0m     [\u001b[39m8\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m],\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=279'>280</a>\u001b[0m     [\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m3\u001b[39m,\u001b[39m6\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m],\n\u001b[0;32m   (...)\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=286'>287</a>\u001b[0m     [\u001b[39m0\u001b[39m,\u001b[39m9\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m4\u001b[39m,\u001b[39m0\u001b[39m,\u001b[39m0\u001b[39m]\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=287'>288</a>\u001b[0m ]\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=288'>289</a>\u001b[0m llist \u001b[39m=\u001b[39m SudokuSolver(sudoku)\n\u001b[0;32m--> <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=289'>290</a>\u001b[0m get_ipython()\u001b[39m.\u001b[39;49mrun_line_magic(\u001b[39m'\u001b[39;49m\u001b[39mprun\u001b[39;49m\u001b[39m'\u001b[39;49m, \u001b[39m'\u001b[39;49m\u001b[39mllist.FillInSudoku(llist.SudokuSolve())\u001b[39;49m\u001b[39m'\u001b[39;49m)\n",
      "File \u001b[0;32m~/anaconda3/envs/py38/lib/python3.8/site-packages/IPython/core/interactiveshell.py:2305\u001b[0m, in \u001b[0;36mInteractiveShell.run_line_magic\u001b[0;34m(self, magic_name, line, _stack_depth)\u001b[0m\n\u001b[1;32m   2303\u001b[0m     kwargs[\u001b[39m'\u001b[39m\u001b[39mlocal_ns\u001b[39m\u001b[39m'\u001b[39m] \u001b[39m=\u001b[39m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mget_local_scope(stack_depth)\n\u001b[1;32m   2304\u001b[0m \u001b[39mwith\u001b[39;00m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mbuiltin_trap:\n\u001b[0;32m-> 2305\u001b[0m     result \u001b[39m=\u001b[39m fn(\u001b[39m*\u001b[39;49margs, \u001b[39m*\u001b[39;49m\u001b[39m*\u001b[39;49mkwargs)\n\u001b[1;32m   2306\u001b[0m \u001b[39mreturn\u001b[39;00m result\n",
      "File \u001b[0;32m~/anaconda3/envs/py38/lib/python3.8/site-packages/IPython/core/magics/execution.py:296\u001b[0m, in \u001b[0;36mExecutionMagics.prun\u001b[0;34m(self, parameter_s, cell)\u001b[0m\n\u001b[1;32m    294\u001b[0m     arg_str \u001b[39m+\u001b[39m\u001b[39m=\u001b[39m \u001b[39m'\u001b[39m\u001b[39m\\n\u001b[39;00m\u001b[39m'\u001b[39m \u001b[39m+\u001b[39m cell\n\u001b[1;32m    295\u001b[0m arg_str \u001b[39m=\u001b[39m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mshell\u001b[39m.\u001b[39mtransform_cell(arg_str)\n\u001b[0;32m--> 296\u001b[0m \u001b[39mreturn\u001b[39;00m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49m_run_with_profiler(arg_str, opts, \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mshell\u001b[39m.\u001b[39;49muser_ns)\n",
      "File \u001b[0;32m~/anaconda3/envs/py38/lib/python3.8/site-packages/IPython/core/magics/execution.py:318\u001b[0m, in \u001b[0;36mExecutionMagics._run_with_profiler\u001b[0;34m(self, code, opts, namespace)\u001b[0m\n\u001b[1;32m    316\u001b[0m prof \u001b[39m=\u001b[39m profile\u001b[39m.\u001b[39mProfile()\n\u001b[1;32m    317\u001b[0m \u001b[39mtry\u001b[39;00m:\n\u001b[0;32m--> 318\u001b[0m     prof \u001b[39m=\u001b[39m prof\u001b[39m.\u001b[39;49mrunctx(code, namespace, namespace)\n\u001b[1;32m    319\u001b[0m     sys_exit \u001b[39m=\u001b[39m \u001b[39m'\u001b[39m\u001b[39m'\u001b[39m\n\u001b[1;32m    320\u001b[0m \u001b[39mexcept\u001b[39;00m \u001b[39mSystemExit\u001b[39;00m:\n",
      "File \u001b[0;32m~/anaconda3/envs/py38/lib/python3.8/cProfile.py:100\u001b[0m, in \u001b[0;36mProfile.runctx\u001b[0;34m(self, cmd, globals, locals)\u001b[0m\n\u001b[1;32m     98\u001b[0m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39menable()\n\u001b[1;32m     99\u001b[0m \u001b[39mtry\u001b[39;00m:\n\u001b[0;32m--> 100\u001b[0m     exec(cmd, \u001b[39mglobals\u001b[39;49m, \u001b[39mlocals\u001b[39;49m)\n\u001b[1;32m    101\u001b[0m \u001b[39mfinally\u001b[39;00m:\n\u001b[1;32m    102\u001b[0m     \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mdisable()\n",
      "File \u001b[0;32m<string>:1\u001b[0m, in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n",
      "\u001b[1;32m/Users/apple/Desktop/Python 储蓄罐/Untitled Folder/Soduku.ipynb Cell 7\u001b[0m in \u001b[0;36mSudokuSolver.SudokuSolve\u001b[0;34m(self, k, solution, size_heuristic)\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=234'>235</a>\u001b[0m     \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mCoverColumn(j\u001b[39m.\u001b[39mcolumn)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=235'>236</a>\u001b[0m     j \u001b[39m=\u001b[39m j\u001b[39m.\u001b[39mright\n\u001b[0;32m--> <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=237'>238</a>\u001b[0m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mSudokuSolve(k\u001b[39m=\u001b[39;49mk\u001b[39m+\u001b[39;49m\u001b[39m1\u001b[39;49m, solution\u001b[39m=\u001b[39;49msolution)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=239'>240</a>\u001b[0m r \u001b[39m=\u001b[39m solution[k]\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=240'>241</a>\u001b[0m c \u001b[39m=\u001b[39m r\u001b[39m.\u001b[39mcolumn\n",
      "\u001b[1;32m/Users/apple/Desktop/Python 储蓄罐/Untitled Folder/Soduku.ipynb Cell 7\u001b[0m in \u001b[0;36mSudokuSolver.SudokuSolve\u001b[0;34m(self, k, solution, size_heuristic)\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=234'>235</a>\u001b[0m     \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mCoverColumn(j\u001b[39m.\u001b[39mcolumn)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=235'>236</a>\u001b[0m     j \u001b[39m=\u001b[39m j\u001b[39m.\u001b[39mright\n\u001b[0;32m--> <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=237'>238</a>\u001b[0m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mSudokuSolve(k\u001b[39m=\u001b[39;49mk\u001b[39m+\u001b[39;49m\u001b[39m1\u001b[39;49m, solution\u001b[39m=\u001b[39;49msolution)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=239'>240</a>\u001b[0m r \u001b[39m=\u001b[39m solution[k]\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=240'>241</a>\u001b[0m c \u001b[39m=\u001b[39m r\u001b[39m.\u001b[39mcolumn\n",
      "    \u001b[0;31m[... skipping similar frames: SudokuSolver.SudokuSolve at line 238 (24 times)]\u001b[0m\n",
      "\u001b[1;32m/Users/apple/Desktop/Python 储蓄罐/Untitled Folder/Soduku.ipynb Cell 7\u001b[0m in \u001b[0;36mSudokuSolver.SudokuSolve\u001b[0;34m(self, k, solution, size_heuristic)\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=234'>235</a>\u001b[0m     \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mCoverColumn(j\u001b[39m.\u001b[39mcolumn)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=235'>236</a>\u001b[0m     j \u001b[39m=\u001b[39m j\u001b[39m.\u001b[39mright\n\u001b[0;32m--> <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=237'>238</a>\u001b[0m \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mSudokuSolve(k\u001b[39m=\u001b[39;49mk\u001b[39m+\u001b[39;49m\u001b[39m1\u001b[39;49m, solution\u001b[39m=\u001b[39;49msolution)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=239'>240</a>\u001b[0m r \u001b[39m=\u001b[39m solution[k]\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=240'>241</a>\u001b[0m c \u001b[39m=\u001b[39m r\u001b[39m.\u001b[39mcolumn\n",
      "\u001b[1;32m/Users/apple/Desktop/Python 储蓄罐/Untitled Folder/Soduku.ipynb Cell 7\u001b[0m in \u001b[0;36mSudokuSolver.SudokuSolve\u001b[0;34m(self, k, solution, size_heuristic)\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=242'>243</a>\u001b[0m j \u001b[39m=\u001b[39m r\u001b[39m.\u001b[39mleft\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=243'>244</a>\u001b[0m \u001b[39mwhile\u001b[39;00m j \u001b[39m!=\u001b[39m r:\n\u001b[0;32m--> <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=244'>245</a>\u001b[0m     \u001b[39mself\u001b[39;49m\u001b[39m.\u001b[39;49mUncoverColumn(j\u001b[39m.\u001b[39;49mcolumn)\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=245'>246</a>\u001b[0m     j \u001b[39m=\u001b[39m j\u001b[39m.\u001b[39mleft\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=247'>248</a>\u001b[0m r \u001b[39m=\u001b[39m r\u001b[39m.\u001b[39mdown\n",
      "\u001b[1;32m/Users/apple/Desktop/Python 储蓄罐/Untitled Folder/Soduku.ipynb Cell 7\u001b[0m in \u001b[0;36mSudokuSolver.UncoverColumn\u001b[0;34m(self, c)\u001b[0m\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=199'>200</a>\u001b[0m         j\u001b[39m.\u001b[39mup\u001b[39m.\u001b[39mdown \u001b[39m=\u001b[39m j\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=200'>201</a>\u001b[0m         j \u001b[39m=\u001b[39m j\u001b[39m.\u001b[39mleft\n\u001b[0;32m--> <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=201'>202</a>\u001b[0m     i \u001b[39m=\u001b[39m i\u001b[39m.\u001b[39;49mup\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=202'>203</a>\u001b[0m c\u001b[39m.\u001b[39mright\u001b[39m.\u001b[39mleft \u001b[39m=\u001b[39m c\n\u001b[1;32m    <a href='vscode-notebook-cell:/Users/apple/Desktop/Python%20%E5%82%A8%E8%93%84%E7%BD%90/Untitled%20Folder/Soduku.ipynb#W6sZmlsZQ%3D%3D?line=203'>204</a>\u001b[0m c\u001b[39m.\u001b[39mleft\u001b[39m.\u001b[39mright \u001b[39m=\u001b[39m c\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "from time import perf_counter\n",
    "from copy import copy\n",
    "\n",
    "# SUDOKU GRID\n",
    "sudoku = [[0, 7, 0, 9, 4, 2, 0, 1, 0],\n",
    "          [0, 0, 8, 5, 0, 1, 0, 0, 0],\n",
    "          [0, 9, 0, 0, 0, 0, 0, 0, 0],\n",
    "          [8, 3, 0, 0, 0, 0, 0, 0, 0],\n",
    "          [6, 5, 7, 2, 0, 0, 0, 8, 0],\n",
    "          [0, 2, 9, 0, 0, 0, 0, 7, 0],\n",
    "          [0, 8, 0, 1, 9, 0, 0, 0, 0],\n",
    "          [9, 0, 0, 0, 0, 7, 1, 2, 5],\n",
    "          [5, 0, 0, 6, 2, 3, 8, 0, 7]]\n",
    "\n",
    "# HEADER GENERATION\n",
    "\n",
    "def generateColumns(size):\n",
    "    size += 1\n",
    "    row_column = []\n",
    "    for i in range(1, size):\n",
    "        for j in range(1, size):\n",
    "            row_column.append('R'+str(i)+'C'+str(j))\n",
    "    row_number = []\n",
    "    for i in range(1,size):\n",
    "        for j in range(1, size):\n",
    "            row_number.append('R'+str(i)+'#'+str(j))\n",
    "    column_number = []\n",
    "    for i in range(1, size):\n",
    "        for j in range(1, size):\n",
    "            column_number.append('C'+str(i)+'#'+str(j))\n",
    "    box_number = []\n",
    "    for i in range(1, size):\n",
    "        for j in range(1, size):\n",
    "            box_number.append('B'+str(i)+'#'+str(j))\n",
    "\n",
    "    return row_column + row_number + column_number + box_number\n",
    "\n",
    "# ROW GENERATION\n",
    "# DOES NOT CURRENTLY WORK FOR NUMBERS OTHER THAN 9\n",
    "def generateRows(size, X):\n",
    "    final = []\n",
    "    for row in range(size):\n",
    "        for column in range(size):\n",
    "            for cell in range(size):\n",
    "                temp = []\n",
    "                # Add Row-Column\n",
    "                temp.append(X[row*size + column])\n",
    "                # Add Row-Number\n",
    "                temp.append(X[size**2 + row*size + cell])\n",
    "                # Add Column-Number\n",
    "                temp.append(X[((size**2)*2) + column*size + cell])\n",
    "                # Add Box-Number\n",
    "                box = 0\n",
    "                if row > 2:\n",
    "                    box += 3\n",
    "                if row > 5:\n",
    "                    box += 3\n",
    "                if column > 2:\n",
    "                    box += 1\n",
    "                if column > 5:\n",
    "                    box += 1\n",
    "                temp.append(X[((size**2)*3) + box*size + cell])\n",
    "                final.append(temp)\n",
    "    return final\n",
    "\n",
    "class Node:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.right = None\n",
    "        self.left = None\n",
    "        self.up = None\n",
    "        self.down = None\n",
    "        self.column = None\n",
    "\n",
    "class ColumnNode:\n",
    "\n",
    "    def __init__(self, name):\n",
    "            self.name = name\n",
    "            self.right = None\n",
    "            self.left = None\n",
    "            self.up = None\n",
    "            self.down = None\n",
    "            self.size = None\n",
    "\n",
    "class SudokuSolver:\n",
    "\n",
    "    def __init__(self, sudoku):\n",
    "        self.header = ColumnNode('Header')\n",
    "        self.sudoku = sudoku\n",
    "        self.constraints = generateColumns(9)\n",
    "        self.rows = generateRows(9, self.constraints)\n",
    "\n",
    "        self.solution = {}\n",
    "        self.solution_key = 0\n",
    "\n",
    "        \n",
    "        # For each constraint, make a column.\n",
    "        tic = perf_counter()\n",
    "        temp_column = self.header\n",
    "        for column in self.constraints:\n",
    "            temp_column.right = ColumnNode(column)\n",
    "            temp_column.right.left = temp_column\n",
    "            temp_column = temp_column.right\n",
    "        temp_column.right = self.header\n",
    "        self.header.left = temp_column\n",
    "\n",
    "        # For each row, go across and add one node down.\n",
    "        for row in self.rows:\n",
    "            first_node = None\n",
    "            previous_node = None\n",
    "            for item in row:\n",
    "                temp_column = self.header.right\n",
    "                while temp_column != self.header:\n",
    "                    if item == temp_column.name:\n",
    "                        #print(\"Placing a node in Node \" + temp_column.name)\n",
    "                        temp = temp_column\n",
    "                        while temp.down != None:\n",
    "                            temp = temp.down\n",
    "                        temp.down = Node()\n",
    "                        if first_node == None:\n",
    "                            first_node = temp.down\n",
    "                        if previous_node != None:\n",
    "                            temp.down.left = previous_node\n",
    "                            temp.down.left.right = temp.down\n",
    "                        temp.down.up = temp\n",
    "                        temp.down.column = temp_column\n",
    "                        previous_node = temp.down\n",
    "                        break\n",
    "                    temp_column = temp_column.right\n",
    "            first_node.left = previous_node\n",
    "            previous_node.right = first_node\n",
    "\n",
    "            #print('\\n')\n",
    "\n",
    "        # Link up each bottom node with their header node.\n",
    "        temp = self.header.right\n",
    "        while temp != self.header:\n",
    "            size = 0\n",
    "            while temp.down != None:\n",
    "                size += 1\n",
    "                temp = temp.down\n",
    "            temp.column.size = size\n",
    "            temp.down = temp.column\n",
    "            temp.down.up = temp\n",
    "            temp = temp.down.right\n",
    "\n",
    "        toc = perf_counter()\n",
    "        self.SolvedLinkRemoval()\n",
    "        print(f\"Linked list made in {toc - tic:0.4f} seconds.\")\n",
    "\n",
    "    def SolvedLinkRemoval(self):\n",
    "\n",
    "        self.solved_parts = []\n",
    "        self.rows_to_remove = []\n",
    "\n",
    "        for row in self.sudoku:\n",
    "            for digit in row:\n",
    "                if digit != 0:\n",
    "                    self.solved_parts.append((self.sudoku.index(row) + 1, row.index(digit) + 1, digit))\n",
    "\n",
    "        for row, column, digit in self.solved_parts:\n",
    "            temp = self.header.right\n",
    "            temp_name = 'R'+str(row)+'C'+str(column)\n",
    "            while temp != self.header:\n",
    "                if temp.name == temp_name:\n",
    "                    for i in range(digit):\n",
    "                        temp = temp.down\n",
    "                    self.rows_to_remove.append(temp)\n",
    "                    break\n",
    "                temp = temp.right\n",
    "\n",
    "        for node in self.rows_to_remove:\n",
    "            self.CoverColumn(node.column)\n",
    "            j = node.right\n",
    "            while j != node:\n",
    "                self.CoverColumn(j.column)\n",
    "                j = j.right\n",
    "\n",
    "    def CoverColumn(self, c):\n",
    "        c.right.left = c.left\n",
    "        c.left.right = c.right\n",
    "        i = c.down\n",
    "        while i != c:\n",
    "            j = i.right\n",
    "            while j != i:\n",
    "                j.down.up = j.up\n",
    "                j.up.down = j.down\n",
    "                j.column.size = j.column.size - 1\n",
    "                j = j.right\n",
    "            i = i.down\n",
    "\n",
    "\n",
    "    def UncoverColumn(self, c):\n",
    "        i = c.up\n",
    "        while i != c:\n",
    "            j = i.left\n",
    "            while j != i:\n",
    "                j.column.size = j.column.size + 1\n",
    "                j.down.up = j\n",
    "                j.up.down = j\n",
    "                j = j.left\n",
    "            i = i.up\n",
    "        c.right.left = c\n",
    "        c.left.right = c\n",
    "\n",
    "    def SudokuSolve(self, k=0, solution={}, size_heuristic=False):\n",
    "\n",
    "        if self.header == self.header.right:\n",
    "            self.solution[self.solution_key] = []\n",
    "            for o in solution.values():\n",
    "                self.solution[self.solution_key].append(o.column.name + o.right.column.name[-2:])\n",
    "            self.solution_key += 1\n",
    "            return\n",
    "        else:\n",
    "            # Choose column c...\n",
    "            if size_heuristic: \n",
    "                s = float('inf')\n",
    "                j = self.header.right\n",
    "                while j != self.header:\n",
    "                    if j.size < s:\n",
    "                        c = j\n",
    "                        s = j.size\n",
    "                    j = j.right\n",
    "            else:\n",
    "                c = self.header.right\n",
    "            # ...and cover it.\n",
    "            self.CoverColumn(c)\n",
    "            # For each r below c, make r the k-th part of the solution.\n",
    "            r = c.down\n",
    "            while r != c:\n",
    "                solution[k] = r\n",
    "\n",
    "                j = r.right\n",
    "                while j != r:\n",
    "                    self.CoverColumn(j.column)\n",
    "                    j = j.right\n",
    "\n",
    "                self.SudokuSolve(k=k+1, solution=solution)\n",
    "\n",
    "                r = solution[k]\n",
    "                c = r.column\n",
    "\n",
    "                j = r.left\n",
    "                while j != r:\n",
    "                    self.UncoverColumn(j.column)\n",
    "                    j = j.left\n",
    "\n",
    "                r = r.down\n",
    "            \n",
    "            self.UncoverColumn(c)\n",
    "\n",
    "            if k == 0:\n",
    "                return (self.solution)\n",
    "\n",
    "            return\n",
    "\n",
    "    def FillInSudoku(self, solutions_dict):\n",
    "\n",
    "        number = 1\n",
    "        for solution in solutions_dict.values():\n",
    "            for cell in solution:\n",
    "                # cell is a string like 'R1C1#1'\n",
    "                # cell[1] is the row + 1\n",
    "                row = int(cell[1]) - 1\n",
    "                # cell[3] is the column + 1\n",
    "                column = int(cell[3]) - 1\n",
    "                # cell[5] is the digit\n",
    "                digit = int(cell[5])\n",
    "                self.sudoku[row][column] = digit\n",
    "            print(f'Solution #{number}')\n",
    "            for i in self.sudoku:\n",
    "                print(i)\n",
    "            print('')\n",
    "            number += 1\n",
    "\n",
    "\n",
    "# Test = \"800000000003600000070090200050007000000045700000100030001000068008500010090000400\"\n",
    "sudoku = [\n",
    "    [8,0,0,0,0,0,0,0,0],\n",
    "    [0,0,3,6,0,0,0,0,0],\n",
    "    [0,7,0,0,9,0,2,0,0],\n",
    "    [0,5,0,0,0,7,0,0,0],\n",
    "    [0,0,0,0,4,5,7,0,0],\n",
    "    [0,0,0,1,0,0,0,3,0],\n",
    "    [0,0,1,0,0,0,0,6,8],\n",
    "    [0,0,8,5,0,0,0,1,0],\n",
    "    [0,9,0,0,0,0,4,0,0]\n",
    "]\n",
    "llist = SudokuSolver(sudoku)\n",
    "%prun llist.FillInSudoku(llist.SudokuSolve())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[8, 1, 2, 7, 5, 3, 6, 4, 9], [9, 4, 3, 6, 8, 2, 1, 7, 5], [6, 7, 5, 4, 9, 1, 2, 8, 3], [1, 5, 4, 2, 3, 7, 8, 9, 6], [3, 6, 9, 8, 4, 5, 7, 2, 1], [2, 8, 7, 1, 6, 9, 5, 3, 4], [5, 2, 1, 9, 7, 4, 3, 6, 8], [4, 3, 8, 5, 2, 6, 9, 1, 7], [7, 9, 6, 3, 1, 8, 4, 5, 2]]\n",
      " "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         309848 function calls (247885 primitive calls) in 1.019 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "    61964    0.542    0.000    0.804    0.000 354830788.py:20(value)\n",
      "    61964    0.225    0.000    0.225    0.000 354830788.py:25(<listcomp>)\n",
      "  61964/1    0.152    0.000    1.017    1.017 354830788.py:38(try_sudoku)\n",
      "    61964    0.061    0.000    0.061    0.000 354830788.py:8(get_next)\n",
      "    61964    0.037    0.000    0.037    0.000 354830788.py:26(<listcomp>)\n",
      "        1    0.001    0.001    0.001    0.001 socket.py:543(send)\n",
      "        1    0.000    0.000    1.019    1.019 {built-in method builtins.exec}\n",
      "        2    0.000    0.000    0.001    0.000 iostream.py:525(write)\n",
      "        1    0.000    0.000    0.001    0.001 {built-in method builtins.print}\n",
      "        1    0.000    0.000    0.001    0.001 iostream.py:209(schedule)\n",
      "        1    0.000    0.000    1.018    1.018 354830788.py:52(sudoku)\n",
      "        2    0.000    0.000    0.000    0.000 iostream.py:436(_is_master_process)\n",
      "        1    0.000    0.000    0.000    0.000 threading.py:1071(is_alive)\n",
      "        2    0.000    0.000    0.001    0.000 iostream.py:455(_schedule_flush)\n",
      "        1    0.000    0.000    0.000    0.000 threading.py:1017(_wait_for_tstate_lock)\n",
      "        1    0.000    0.000    0.000    0.000 354830788.py:30(start_pos)\n",
      "        1    0.000    0.000    0.000    0.000 iostream.py:97(_event_pipe)\n",
      "        2    0.000    0.000    0.000    0.000 {method 'write' of '_io.StringIO' objects}\n",
      "        1    0.000    0.000    1.018    1.018 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'acquire' of '_thread.lock' objects}\n",
      "        2    0.000    0.000    0.000    0.000 {built-in method posix.getpid}\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "        2    0.000    0.000    0.000    0.000 {built-in method builtins.len}\n",
      "        2    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}\n",
      "        1    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}\n",
      "        1    0.000    0.000    0.000    0.000 threading.py:513(is_set)"
     ]
    }
   ],
   "source": [
    "import random \n",
    "import sys  \n",
    "sys.setrecursionlimit(100000) # 发现python默认的递归深度是很有限的\n",
    "                              #（默认是1000），因此当递归深度超过999的\n",
    "                              # 样子，就会引发这样的一个异常。\n",
    "\n",
    "\n",
    "def get_next(m:\"数独矩阵\", x:\"空白格行数\", y:\"空白格列数\"):\n",
    "    \"\"\" 功能：获得下一个空白格在数独中的坐标。       \n",
    "    \"\"\"\n",
    "    for next_y in range(y+1, 9):  # 下一个空白格和当前格在一行的情况\n",
    "        if m[x][next_y] == 0:\n",
    "            return x, next_y\n",
    "    for next_x in range(x+1, 9):  # 下一个空白格和当前格不在一行的情况\n",
    "        for next_y in range(0, 9):\n",
    "            if m[next_x][next_y] == 0:\n",
    "                return next_x, next_y\n",
    "    return -1, -1               # 若不存在下一个空白格，则返回 -1，-1\n",
    "\n",
    "def value(m:\"数独矩阵\", x:\"空白格行数\", y:\"空白格列数\"):\n",
    "    \"\"\" 功能：返回符合\"每个横排和竖排以及\n",
    "              九宫格内无相同数字\"这个条件的有效值。\n",
    "    \"\"\" \n",
    "    i, j = x//3, y//3\n",
    "    grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]\n",
    "    v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \\\n",
    "        set(list(zip(*m))[y])    \n",
    "    return list(v)\n",
    "\n",
    "def start_pos(m:\"数独矩阵\"):\n",
    "    \"\"\" 功能：返回第一个空白格的位置坐标\"\"\"\n",
    "    for x in range(9):\n",
    "        for y in range(9):\n",
    "            if m[x][y] == 0:\n",
    "                return x, y\n",
    "    return False, False  # 若数独已完成，则返回 False, False\n",
    "\n",
    "def try_sudoku(m:\"数独矩阵\", x:\"空白格行数\", y:\"空白格列数\"):\n",
    "    \"\"\" 功能：试着填写数独 \"\"\"\n",
    "    for v in value(m, x, y):\n",
    "        m[x][y] = v\n",
    "        next_x, next_y = get_next(m, x, y)\n",
    "        if next_y == -1: # 如果无下一个空白格\n",
    "            return True\n",
    "        else:\n",
    "            end = try_sudoku(m, next_x, next_y) # 递归\n",
    "            if end:\n",
    "                return True\n",
    "            m[x][y] = 0 # 在递归的过程中，如果数独没有解开，\n",
    "                        # 则回溯到上一个空白格\n",
    "\n",
    "def sudoku(m):        \n",
    "    x, y = start_pos(m)\n",
    "    try_sudoku(m, x, y)\n",
    "    print(m)     \n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    sudoku2 = [\n",
    "        [8,0,0,0,0,0,0,0,0],\n",
    "        [0,0,3,6,0,0,0,0,0],\n",
    "        [0,7,0,0,9,0,2,0,0],\n",
    "        [0,5,0,0,0,7,0,0,0],\n",
    "        [0,0,0,0,4,5,7,0,0],\n",
    "        [0,0,0,1,0,0,0,3,0],\n",
    "        [0,0,1,0,0,0,0,6,8],\n",
    "        [0,0,8,5,0,0,0,1,0],\n",
    "        [0,9,0,0,0,0,4,0,0]\n",
    "    ]\n",
    "\n",
    "    %prun sudoku(sudoku2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HH\n",
      " "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         27477 function calls (25985 primitive calls) in 0.181 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "     1492    0.098    0.000    0.098    0.000 3453978379.py:74(choose_least_column)\n",
      "     5968    0.036    0.000    0.036    0.000 3453978379.py:89(cover)\n",
      "     5644    0.025    0.000    0.025    0.000 3453978379.py:104(uncover)\n",
      "   1493/1    0.013    0.000    0.172    0.172 3453978379.py:118(search)\n",
      "      561    0.003    0.000    0.007    0.000 3453978379.py:47(_create_links)\n",
      "     2569    0.002    0.000    0.002    0.000 3453978379.py:4(__init__)\n",
      "     2244    0.001    0.000    0.001    0.000 3453978379.py:38(_append_to_column)\n",
      "        1    0.001    0.001    0.008    0.008 3453978379.py:18(create_matrix)\n",
      "     1816    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}\n",
      "     2244    0.000    0.000    0.000    0.000 3453978379.py:36(<lambda>)\n",
      "     1411    0.000    0.000    0.000    0.000 {method 'pop' of 'list' objects}\n",
      "        1    0.000    0.000    0.181    0.181 3453978379.py:154(solve)\n",
      "      561    0.000    0.000    0.000    0.000 3453978379.py:35(<lambda>)\n",
      "      325    0.000    0.000    0.000    0.000 3453978379.py:10(__init__)\n",
      "      561    0.000    0.000    0.000    0.000 3453978379.py:34(<lambda>)\n",
      "      561    0.000    0.000    0.000    0.000 3453978379.py:33(<lambda>)\n",
      "        1    0.000    0.000    0.181    0.181 {built-in method builtins.exec}\n",
      "        1    0.000    0.000    0.181    0.181 <string>:1(<module>)\n",
      "       21    0.000    0.000    0.000    0.000 {built-in method builtins.ord}\n",
      "        1    0.000    0.000    0.000    0.000 3453978379.py:15(__init__)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}"
     ]
    }
   ],
   "source": [
    "from math import inf\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, column, row):\n",
    "        self.column = column\n",
    "        self.row = row\n",
    "        self.up, self.down, self.left, self.right = self, self, self, self\n",
    "\n",
    "class ColumnNode(Node):\n",
    "    def __init__(self, id):\n",
    "        Node.__init__(self, self, id)\n",
    "        self.row_count = 0\n",
    "\n",
    "class DLX(object):\n",
    "    def __init__(self):\n",
    "        self.root = ColumnNode(0)\n",
    "\n",
    "    def create_matrix(self, grid_str):\n",
    "        \"\"\"Creates an exact cover matrix from a sudoku grid\"\"\"\n",
    "        root = self.root\n",
    "        cols = [root]\n",
    "        # Construct column headers as a doubly circular linked list\n",
    "        # We'll be storing all the column headers in a list for easy access\n",
    "        for i in range(324):\n",
    "            c = ColumnNode(i + 1)\n",
    "            c.right = root\n",
    "            c.left = root.left\n",
    "            root.left.right = c\n",
    "            root.left = c\n",
    "            cols.append(c)\n",
    "\n",
    "        # These help us find which constraint should be filled in\n",
    "        row_constraint = lambda x, k: 81 + (x // 9) * 9 + k\n",
    "        col_constraint = lambda x, k: 162 + (x % 9) * 9 + k\n",
    "        box_constraint = lambda x, k: 243 + (x // 27) * 27 + (x % 9) // 3 * 9 + k\n",
    "        row_num = lambda x, k: x * 9 + k\n",
    "\n",
    "        def _append_to_column(n):\n",
    "            \"\"\"Appends a row node at the end of a column\"\"\"\n",
    "            c = n.column\n",
    "            c.row_count += 1\n",
    "            n.down = c\n",
    "            n.up = c.up\n",
    "            c.up.down = n\n",
    "            c.up = n\n",
    "\n",
    "        def _create_links(x, k):\n",
    "            \"\"\"Creates links for a row\"\"\"\n",
    "            cell_node = Node(cols[x + 1], row_num(x, k))\n",
    "            row_node = Node(cols[row_constraint(x, k)], row_num(x, k))\n",
    "            col_node = Node(cols[col_constraint(x, k)], row_num(x, k))\n",
    "            box_node = Node(cols[box_constraint(x, k)], row_num(x, k))\n",
    "\n",
    "            # Link all the nodes into a single row\n",
    "            cell_node.right, cell_node.left = row_node, box_node\n",
    "            row_node.right, row_node.left = col_node, cell_node\n",
    "            col_node.right, col_node.left = box_node, row_node\n",
    "            box_node.right, box_node.left = cell_node, col_node\n",
    "\n",
    "            _append_to_column(cell_node)\n",
    "            _append_to_column(row_node)\n",
    "            _append_to_column(col_node)\n",
    "            _append_to_column(box_node)\n",
    "\n",
    "\n",
    "        for index, chr in enumerate(grid_str):\n",
    "            if chr == '.':\n",
    "                # Square is empty, add all possible values\n",
    "                for k in range(9):\n",
    "                    _create_links(index, k + 1)\n",
    "            else:\n",
    "                _create_links(index, ord(chr) - 48)\n",
    "\n",
    "    def choose_least_column(self):\n",
    "        \"\"\"\n",
    "        We use the S heuristic to minimize branching factor\n",
    "        Returns the column with the least number of rows\n",
    "        \"\"\"\n",
    "        c = None\n",
    "        i = self.root.right\n",
    "        s = inf\n",
    "        while i != self.root:\n",
    "            if i.row_count < s:\n",
    "                c = i\n",
    "                s = i.row_count\n",
    "            i = i.right\n",
    "        return c\n",
    "\n",
    "    def cover(self, col):\n",
    "        \"\"\"Removes a column along with all rows that intersect said column\"\"\"\n",
    "        col.right.left = col.left\n",
    "        col.left.right = col.right\n",
    "        i = col.down\n",
    "        while i != col:\n",
    "            # Iterate through nodes in row and unlink them\n",
    "            j = i.right\n",
    "            while j != i:\n",
    "                j.down.up = j.up\n",
    "                j.up.down = j.down\n",
    "                j.column.row_count -= 1\n",
    "                j = j.right\n",
    "            i = i.down\n",
    "\n",
    "    def uncover(self, col):\n",
    "        \"\"\"Undo covering of a column\"\"\"\n",
    "        i = col.up\n",
    "        while i != col:\n",
    "            j = i.left\n",
    "            while j != i:\n",
    "                j.down.up = j\n",
    "                j.up.down = j\n",
    "                j.column.row_count += 1\n",
    "                j = j.left\n",
    "            i = i.up\n",
    "        col.right.left = col\n",
    "        col.left.right = col\n",
    "\n",
    "    def search(self, solution):\n",
    "        \"\"\"Search for a solution from a exact cover matrix\"\"\"\n",
    "\n",
    "        # No columns left, a solution is found\n",
    "        if self.root == self.root.right:\n",
    "            return solution, True\n",
    "\n",
    "        c = self.choose_least_column()\n",
    "        self.cover(c)\n",
    "\n",
    "        i = c.down\n",
    "        while i != c:\n",
    "            solution.append(i)\n",
    "            j = i.right\n",
    "            while j != i:\n",
    "                self.cover(j.column)\n",
    "                j = j.right\n",
    "\n",
    "            solution, found = self.search(solution)\n",
    "            if found:\n",
    "                return solution, True\n",
    "\n",
    "            i = solution.pop()\n",
    "            c = i.column\n",
    "            j = i.left\n",
    "            while j != i:\n",
    "                self.uncover(j.column)\n",
    "                j = j.left\n",
    "\n",
    "            i = i.down\n",
    "\n",
    "        self.uncover(c)\n",
    "        return solution, False\n",
    "\n",
    "\n",
    "class Sudoku(object):\n",
    "    def solve(self, grid_str):\n",
    "        solver = DLX()\n",
    "        solver.create_matrix(grid_str)\n",
    "        dlx_solution, found = solver.search([])\n",
    "        return dlx_solution, found\n",
    "\n",
    "    def output_solution(self, dlx_solution, found):\n",
    "        \"\"\"Converts a solution set from Dancing Links into a grid\"\"\"\n",
    "        if not found:\n",
    "            print('Solution not found')\n",
    "            return\n",
    "        solution = [0] * 81\n",
    "        for i in dlx_solution:\n",
    "            val = i.row % 9\n",
    "            if val == 0:\n",
    "                val = 9\n",
    "            solution[(i.row - 1) // 9] = val\n",
    "        self.output_grid(''.join(str(i) for i in solution))\n",
    "\n",
    "    def output_grid(self, grid_str):\n",
    "        \"\"\"Outputs Sudoku grid in a readable format\"\"\"\n",
    "        print('')\n",
    "        grid = list(grid_str)\n",
    "        row = list('+-------+-------+-------+')\n",
    "        for index, chr in enumerate(grid):\n",
    "            if index % 9 == 0:\n",
    "                print(''.join(row))\n",
    "                if index % 27 == 0 and index > 0:\n",
    "                    print('+-------+-------+-------+')\n",
    "                row = []\n",
    "            if index % 3 == 0:\n",
    "                row.extend(['|', ' '])\n",
    "            row.extend([chr, ' '])\n",
    "            if (index + 1) % 9 == 0:\n",
    "                row.append('|')\n",
    "            if index == len(grid_str) - 1:\n",
    "                print(''.join(row))\n",
    "                print('+-------+-------+-------+\\n')\n",
    "\n",
    "\n",
    "s = Sudoku()\n",
    "# print('Enter a sudoku puzzle in the format shown below:')\n",
    "# print('7......5..5.98472383..2...9.79.58.4...........6.14.97.5...3..94126495.8..4......1\\n')\n",
    "# while 1:\n",
    "print(\"HH\")\n",
    "grid_str = \"800000000003600000070090200050007000000045700000100030001000068008500010090000400\"\n",
    "grid_str = grid_str.replace(\"0\", \".\")\n",
    "%prun solution, found = s.solve(grid_str)\n",
    "# s.output_solution(solution, found)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "+-------+-------+-------+\n",
      "| 8 1 2 | 7 5 3 | 6 4 9 |\n",
      "| 9 4 3 | 6 8 2 | 1 7 5 |\n",
      "| 6 7 5 | 4 9 1 | 2 8 3 |\n",
      "+-------+-------+-------+\n",
      "| 1 5 4 | 2 3 7 | 8 9 6 |\n",
      "| 3 6 9 | 8 4 5 | 7 2 1 |\n",
      "| 2 8 7 | 1 6 9 | 5 3 4 |\n",
      "+-------+-------+-------+\n",
      "| 5 2 1 | 9 7 4 | 3 6 8 |\n",
      "| 4 3 8 | 5 2 6 | 9 1 7 |\n",
      "| 7 9 6 | 3 1 8 | 4 5 2 |\n",
      "+-------+-------+-------+\n",
      "\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         3 function calls in 0.000 seconds\n",
      "\n",
      "   Ordered by: internal time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}\n",
      "        1    0.000    0.000    0.000    0.000 <string>:1(<module>)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}"
     ]
    }
   ],
   "source": [
    "%prun \n",
    "solution, found = s.solve(grid_str)\n",
    "s.output_solution(solution, found)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.13 ('py38')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.13"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "da3096a4b2ddf6e3108983d9c4f8ed6b468b54d4f76a60924a980331cf3af984"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
